Sudoku Solver

Description#

Write a program to solve Sudoku by filling the empty cells. We will be given a 2D array representing a Sudoku puzzle. For a correct solution each of the digits 1-9 must only occur once in each:

Row
Column
Nine 3x3 sub-boxes of the grid

Let us take a look at an example:

Problem

1 of 3

Rule

2 of 3

Solution

3 of 3

Solution#

While solving Sudoku, we will have to take care of two things. First, we place a number at an empty place. The number must not be present in that row, column, or sub-box. So, we will use constrained programming to keep track of which number we can place in a box and which not. Second, let us assume that we have filled a few empty places but, the choice of numbers was not optimal, and we will have to try some other combination. To do that, we will have to use backtracking.

Let us go over the algorithm:

Start filling the board from board[0][0]
If the value is not ‘.’, move on to the next position; otherwise, fill it.
Iterate over each value from 1 to 9:
1. Check if the value is not already present in that row, column, or 3x3 sub-matrix. If no, then move on to the next value; otherwise, move to the next step.
2. Place the value on the board and move to the next position recursively.
3. If we can not place any value from 1 to 9 on a position, then change the value filled in the previous cell and retry.

Let us take a look at an example:

package main
import (
  "fmt"
)
var DIGITS = []byte { '1', '2', '3', '4', '5', '6', '7', '8', '9' }
    
func SolveSudoku(board [][] byte) {
  Solve(board, 0, 0)
}
    
func Solve(board [][]byte, r int, c int) bool{
  // Move right until you get to end, then restart at next row
  if c == 9 { return Solve(board, r + 1, 0) }
  if r == 9 { return true }
        
  if board[r][c] != '.' { return Solve(board, r, c + 1) }
        
  for _, d := range DIGITS {
    if CanPlay(board, r, c, d) {
      board[r][c] = d
      // If can solve remaining then done
      if Solve(board, r, c + 1) { return true }
      // Backtracking
        board[r][c] = '.'
      }
  }
  return false;
}
    
func CanPlay(board [][]byte, r int, c int, x byte) bool {

Enter to Rename, Shift+Enter to Preview

Sudoku solver

Description#

Coding exercise#

Solution#

Complexity measures#

Time complexity#

Space complexity#